🔗 Liste Dinamiche in C

// Definizione di un nodo per lista di interi
typedef struct Nodo {
    int dato;                  // Il valore memorizzato
    struct Nodo *next;       // Puntatore al nodo successivo
} Nodo;

// Nota: Usiamo "struct Nodo *next" perché il tipo Nodo
// non è ancora completamente definito quando dichiariamo next

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// Definizione del nodo
typedef struct Nodo {
    int dato;
    struct Nodo *next;
} Nodo;

// Definizione della lista (opzionale, ma utile)
typedef struct {
    Nodo *head;       // Puntatore al primo nodo
    int dimensione;   // Numero di nodi (opzionale)
} Lista;

// Inizializzazione lista vuota
Lista* crea_lista(void) {
    Lista *lista = (Lista*)malloc(sizeof(Lista));
    if (lista == NULL) {
        fprintf(stderr, "Errore: memoria insufficiente\n");
        return NULL;
    }
    lista->head = NULL;
    lista->dimensione = 0;
    return lista;
}

// Crea un nuovo nodo
Nodo* crea_nodo(int valore) {
    Nodo *nuovo = (Nodo*)malloc(sizeof(Nodo));
    if (nuovo == NULL) {
        fprintf(stderr, "Errore: impossibile creare nodo\n");
        return NULL;
    }
    nuovo->dato = valore;
    nuovo->next = NULL;
    return nuovo;
}

/**
 * @brief Inserisce un nuovo nodo all'inizio della lista
 * @param lista Puntatore alla lista
 * @param valore Valore da inserire
 * @return true se successo, false se errore
 * 
 * Complessità: O(1) - Tempo costante!
 */
bool inserisci_in_testa(Lista *lista, int valore) {
    // 1. Crea nuovo nodo
    Nodo *nuovo = crea_nodo(valore);
    if (nuovo == NULL) {
        return false;
    }
    
    // 2. Il nuovo nodo punta al vecchio head
    nuovo->next = lista->head;
    
    // 3. Il nuovo nodo diventa il nuovo head
    lista->head = nuovo;
    
    // 4. Incrementa dimensione
    lista->dimensione++;
    
    return true;
}

/**
 * @brief Inserisce un nuovo nodo alla fine della lista
 * @param lista Puntatore alla lista
 * @param valore Valore da inserire
 * @return true se successo, false se errore
 * 
 * Complessità: O(n) - Dobbiamo scorrere tutta la lista
 */
bool inserisci_in_coda(Lista *lista, int valore) {
    // Crea nuovo nodo
    Nodo *nuovo = crea_nodo(valore);
    if (nuovo == NULL) {
        return false;
    }
    
    // Caso speciale: lista vuota
    if (lista->head == NULL) {
        lista->head = nuovo;
        lista->dimensione++;
        return true;
    }
    
    // Scorri fino all'ultimo nodo
    Nodo *corrente = lista->head;
    while (corrente->next != NULL) {
        corrente = corrente->next;  // Avanza
    }
    
    // corrente è ora l'ultimo nodo
    // Collegalo al nuovo nodo
    corrente->next = nuovo;
    lista->dimensione++;
    
    return true;
}

/**
 * @brief Inserisce un valore in una posizione specifica (0-indexed)
 * @param lista Puntatore alla lista
 * @param valore Valore da inserire
 * @param posizione Posizione dove inserire (0 = inizio)
 * @return true se successo, false se errore o posizione invalida
 * 
 * Complessità: O(n)
 */
bool inserisci_in_posizione(Lista *lista, int valore, int posizione) {
    // Controllo validità
    if (posizione < 0 || posizione > lista->dimensione) {
        fprintf(stderr, "Posizione invalida\n");
        return false;
    }
    
    // Caso speciale: inserimento in testa
    if (posizione == 0) {
        return inserisci_in_testa(lista, valore);
    }
    
    // Crea nuovo nodo
    Nodo *nuovo = crea_nodo(valore);
    if (nuovo == NULL) return false;
    
    // Scorri fino al nodo PRIMA della posizione
    Nodo *corrente = lista->head;
    for (int i = 0; i < posizione - 1; i++) {
        corrente = corrente->next;
    }
    
    // Inserisci il nuovo nodo
    nuovo->next = corrente->next;  // Nuovo punta a quello dopo
    corrente->next = nuovo;         // Precedente punta a nuovo
    
    lista->dimensione++;
    return true;
}

/**
 * @brief Rimuove e restituisce il primo elemento della lista
 * @param lista Puntatore alla lista
 * @param valore Puntatore dove salvare il valore rimosso (opzionale)
 * @return true se successo, false se lista vuota
 * 
 * Complessità: O(1)
 */
bool rimuovi_testa(Lista *lista, int *valore) {
    if (lista->head == NULL) {
        fprintf(stderr, "Lista vuota\n");
        return false;
    }
    
    // Salva il nodo da rimuovere
    Nodo *da_rimuovere = lista->head;
    
    // Salva il valore (se richiesto)
    if (valore != NULL) {
        *valore = da_rimuovere->dato;
    }
    
    // Sposta head al nodo successivo
    lista->head = da_rimuovere->next;
    
    // Libera memoria del nodo rimosso
    free(da_rimuovere);
    
    lista->dimensione--;
    return true;
}

/**
 * @brief Rimuove la prima occorrenza di un valore
 * @param lista Puntatore alla lista
 * @param valore Valore da cercare e rimuovere
 * @return true se trovato e rimosso, false altrimenti
 * 
 * Complessità: O(n)
 */
bool rimuovi_valore(Lista *lista, int valore) {
    if (lista->head == NULL) {
        return false;
    }
    
    // Caso speciale: il valore è in testa
    if (lista->head->dato == valore) {
        Nodo *temp = lista->head;
        lista->head = lista->head->next;
        free(temp);
        lista->dimensione--;
        return true;
    }
    
    // Cerca il valore
    Nodo *corrente = lista->head;
    while (corrente->next != NULL) {
        if (corrente->next->dato == valore) {
            // Trovato! Rimuovi il nodo successivo
            Nodo *da_rimuovere = corrente->next;
            corrente->next = da_rimuovere->next;  // Scavalca il nodo
            free(da_rimuovere);
            lista->dimensione--;
            return true;
        }
        corrente = corrente->next;
    }
    
    return false;  // Non trovato
}

/**
 * @brief Cerca un valore nella lista
 * @param lista Puntatore alla lista
 * @param valore Valore da cercare
 * @return Puntatore al nodo se trovato, NULL altrimenti
 * 
 * Complessità: O(n)
 */
Nodo* cerca(Lista *lista, int valore) {
    Nodo *corrente = lista->head;
    
    while (corrente != NULL) {
        if (corrente->dato == valore) {
            return corrente;  // Trovato!
        }
        corrente = corrente->next;
    }
    
    return NULL;  // Non trovato
}

/**
 * @brief Conta quante volte appare un valore
 */
int conta_occorrenze(Lista *lista, int valore) {
    int count = 0;
    Nodo *corrente = lista->head;
    
    while (corrente != NULL) {
        if (corrente->dato == valore) {
            count++;
        }
        corrente = corrente->next;
    }
    
    return count;
}

/**
 * @brief Stampa tutti gli elementi della lista
 */
void stampa_lista(Lista *lista) {
    if (lista->head == NULL) {
        printf("Lista vuota\n");
        return;
    }
    
    printf("Lista: ");
    Nodo *corrente = lista->head;
    
    while (corrente != NULL) {
        printf("%d", corrente->dato);
        
        if (corrente->next != NULL) {
            printf(" -> ");
        }
        
        corrente = corrente->next;
    }
    
    printf(" -> NULL\n");
}

/**
 * @brief Stampa con indirizzi di memoria (per debug)
 */
void stampa_lista_debug(Lista *lista) {
    printf("=== DEBUG LISTA ===\n");
    printf("Dimensione: %d\n", lista->dimensione);
    printf("Head: %p\n", (void*)lista->head);
    
    Nodo *corrente = lista->head;
    int i = 0;
    
    while (corrente != NULL) {
        printf("Nodo %d: [dato=%d, addr=%p, next=%p]\n",
               i++, corrente->dato, 
               (void*)corrente, 
               (void*)corrente->next);
        corrente = corrente->next;
    }
    printf("==================\n");
}

// Definizione nodo per lista doppia
typedef struct NodoDouble {
    int dato;
    struct NodoDouble *next;  // Puntatore al successivo
    struct NodoDouble *prev;  // Puntatore al precedente
} NodoDouble;

typedef struct {
    NodoDouble *head;
    NodoDouble *tail;  // Utile per inserimento in coda O(1)
    int dimensione;
} ListaDouble;

bool inserisci_in_testa_double(ListaDouble *lista, int valore) {
    NodoDouble *nuovo = (NodoDouble*)malloc(sizeof(NodoDouble));
    if (nuovo == NULL) return false;
    
    nuovo->dato = valore;
    nuovo->prev = NULL;
    nuovo->next = lista->head;
    
    if (lista->head != NULL) {
        lista->head->prev = nuovo;  // ← Differenza chiave!
    } else {
        lista->tail = nuovo;  // Lista era vuota
    }
    
    lista->head = nuovo;
    lista->dimensione++;
    return true;
}

// ❌ ERRORE GRAVE - Memory leak
Nodo *head = crea_nodo(10);
head = crea_nodo(20);  // ❌ Perso il primo nodo!

// Il primo nodo (10) è ancora in memoria ma irraggiungibile
// → MEMORY LEAK!

// ❌ ERRORE - Libera solo il primo nodo
void distruggi_lista_sbagliato(Lista *lista) {
    free(lista->head);  // ❌ E gli altri nodi???
    free(lista);
}

// ✅ CORRETTO - Libera tutti i nodi
void distruggi_lista(Lista *lista) {
    Nodo *corrente = lista->head;
    
    while (corrente != NULL) {
        Nodo *temp = corrente;
        corrente = corrente->next;  // Salva next PRIMA di free!
        free(temp);
    }
    
    free(lista);
}

/**
 * @brief Rileva se c'è un ciclo nella lista (Floyd's Algorithm)
 * @return true se c'è un ciclo, false altrimenti
 * 
 * Algoritmo della "Tartaruga e Lepre":
 * - Tartaruga: avanza di 1 nodo
 * - Lepre: avanza di 2 nodi
 * Se si incontrano → c'è un ciclo!
 */
bool ha_ciclo(Lista *lista) {
    if (lista->head == NULL) return false;
    
    Nodo *tartaruga = lista->head;
    Nodo *lepre = lista->head;
    
    while (lepre != NULL && lepre->next != NULL) {
        tartaruga = tartaruga->next;        // +1
        lepre = lepre->next->next;          // +2
        
        if (tartaruga == lepre) {
            return true;  // Si sono incontrate! Ciclo!
        }
    }
    
    return false;  // Nessun ciclo
}

/**
 * @brief Inverte una lista sul posto (in-place)
 * @param lista Puntatore alla lista da invertire
 * 
 * Complessità: O(n) tempo, O(1) spazio
 */
void inverti_lista(Lista *lista) {
    Nodo *prev = NULL;
    Nodo *corrente = lista->head;
    Nodo *next = NULL;
    
    while (corrente != NULL) {
        // Salva il prossimo
        next = corrente->next;
        
        // Inverti il puntatore
        corrente->next = prev;
        
        // Avanza
        prev = corrente;
        corrente = next;
    }
    
    // prev è ora l'ultimo nodo (nuovo head)
    lista->head = prev;
}

/**
 * @brief Unisce due liste ordinate in una lista ordinata
 * @return Puntatore alla testa della lista unita
 * 
 * Complessità: O(n + m)
 */
Nodo* merge_liste_ordinate(Nodo *l1, Nodo *l2) {
    // Caso base
    if (l1 == NULL) return l2;
    if (l2 == NULL) return l1;
    
    Nodo *risultato = NULL;
    
    // Scegli il più piccolo come head
    if (l1->dato <= l2->dato) {
        risultato = l1;
        risultato->next = merge_liste_ordinate(l1->next, l2);
    } else {
        risultato = l2;
        risultato->next = merge_liste_ordinate(l1, l2->next);
    }
    
    return risultato;
}

/**
 * @brief Trova il nodo centrale della lista
 * Usa tecnica "fast & slow pointer"
 * 
 * Complessità: O(n) con un solo passaggio!
 */
Nodo* trova_medio(Lista *lista) {
    if (lista->head == NULL) return NULL;
    
    Nodo *slow = lista->head;  // Avanza di 1
    Nodo *fast = lista->head;  // Avanza di 2
    
    while (fast->next != NULL && fast->next->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    
    // Quando fast arriva alla fine, slow è al centro!
    return slow;
}